基于量子双向RRT算法的多平台反舰导弹协同航路规划

针对反舰导弹航路规划面临的动态威胁环境和多平台协同打击问题,提出了一种基于量子双向RRT算法的反舰导弹协同航路规划方法。采用动态坐标设置动态威胁,实时地避开动态威胁;通过取预规划终点方法,实现对目标的时间和空间协同打击;结合量子进化思想,将RRT算法中的扩展方向量子化表示,提出了一种量子双向RRT算法,并应用于航路规划。仿真结果表明,该方法可有效规避动态威胁和解决多平台反舰导弹航路规划的协同问题,并显著地改善了RRT算法的全局收敛性,得到了航程更短的航路。     

云平台上基于关键路径截取的有向无环图应用调度算法

针对云平台上有向无环图科学应用执行容易产生虚拟机资源过剩、资源使用率低及费用虚高的问题,给出一种基于关键路径截取的有向无环图应用调度算法。该算法采取关键路径截取技术,循环找出最晚完成的未分配任务,从该任务出发,在所有未分配任务构成的图中找出最大连通子图,并计算该子图的关键路径,然后将关键路径上的任务集调度到性能匹配的虚拟机上执行;同时通过任务回填技术充分利用虚拟机的空闲时间槽,提高资源使用率。实验结果表明,在云计算平台上,该算法不仅能够在截止时间内完成有向无环图科学应用,而且可以提高资源使用率,有效减少完成该应用所需整体费用。     

Preemptive parallel‐machine scheduling with a common server to minimize makespan

We consider parallel‐machine scheduling with a common server and job preemption to minimize the makespan. While the non‐preemptive version of the problem is strongly NP‐hard, the complexity status of the preemptive version has remained open. We show that the preemptive version is NP‐hard even if there is a fixed number of machines. We give a pseudo‐polynomial time algorithm to solve the case with two machines. We show that the case with an arbitrary number of machines is unary NP‐hard, analyze the performance ratios of some natural heuristic algorithms, and present several solvable special cases. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 388–398, 2017     

On matched active redundancy allocation for coherent systems with statistically dependent component lifetimes

This study addresses the allocation of matched active redundancy components to coherent systems with base components having statistically dependent lifetimes. We consider base component lifetimes and redundancy component lifetimes which are both stochastic arrangement monotone with respect to a pair of components given the lifetimes of the other components. In this context, allocating a more reliable redundancy component to the weaker base component is shown to incur a stochastically larger system lifetime. Numerical examples are presented as an illustration of the theoretical results.     

Parallel machine scheduling with job assignment restrictions

In the classical multiprocessor scheduling problem independent jobs must be assigned to parallel, identical machines with the objective of minimizing the makespan. This article explores the effect of assignment restrictions on the jobs for multiprocessor scheduling problems. This means that each job can only be processed on a specific subset of the machines. Particular attention is given to the case of processing times restricted to one of two values, 1 and λ, differing by at most 2. A matching based polynomial time ε‐approximation algorithm is developed that has a performance ratio tending to . This algorithm is shown to have the best possible performance, tending to 3/2, for processing times 1 and 2. For the special case of nested processing sets, i.e., when the sets of machines upon which individual jobs may be assigned are non‐overlapping, the behavior of list scheduling algorithms is explored. Finally, for assignment restrictions determined by just one characteristic of the machines, such as disc storage or memory constraint in the case of high performance computing, we contribute an algorithm that provides a 3/2 worst case bound and runs in time linear in the number of jobs. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

卫星数传调度模型研究

卫星数传调度问题是一个具有多时间窗口、多资源约束的优化问题。针对该问题,建立了卫星数传需求模型、任务模型和调度模型。在建模过程中,采用了框架模型形式,把问题中的主要约束封闭于每个数传任务中,这在降低调度模型复杂度的同时,也降低了调度算法设计难度。还提出了调度算法设计思想,并设计了一基于灵活度的调度算法。仿真表明,所建立的模型及算法对解决卫星数传调度问题是可行的。     

分段线性凸费用网络流的两个算法

本文讨论了分段线性凸费用网络流问题,推广了线性费用网络流中的负回路方法和最小费用路方法,从而得到了求分段线性凸费用网络的最小费用流的两个算法。     

基于逆向分层的工作流时间-费用优化方法

针对效用网格下基于优先级因子的工作流时间-费用优化问题,基于工作流的同步完成特征对任务进行分层并提出三种实时调度算法:基于逆向分层的sufferage(BLSuff)、基于逆向分层的min-min(BLMin)及基于逆向分层的min-max(BLMax)。算法设计基于优先级因子的衡量标准对时间与费用同时进行优化,并为任务设置期望完成时间以达到充分利用费用优化空间进行费用优化的目标。实验结果表明这三种算法在各种优先级因子下都能对工作流的执行时间与执行费用进行较好的优化。     

机器人集群路径规划技术研究现状

受社会型生物群体行为启发,群体智能得到日益广泛的关注,机器人集群作为群体智能的重要承载者得到了大量研发和广泛应用。机器人集群路径规划技术作为一项核心关键技术也得到快速发展。为此全面深入地调研了机器人集群路径规划的技术发展现状,创新性地归纳了适用于不同集群规模、可扩展性要求、通信需求以及算法要求的集群规划基础计算架构,包括冗余计算架构、分布计算架构和分层计算架构。从可扩展性和适用性角度,分类梳理了最适用于机器人集群的路径规划方法,包括仿生学方法、人工势场法、几何学方法、经典搜索法和进化学习法,并为集群仿真验证研究提供了七款可免费下载或开源的机器人集群仿真验证平台。     

蚁群算法在无人机航路规划中的应用

蚂蚁算法是一种新的源于大自然生物界的仿生随机优化方法。吸收了昆虫中蚂蚁的行为特征,通过其内在的搜索机制,在一系列组合优化问题求解中取得了成效。将蚁群算法应用于无人机(UAV)航路规划,提出了一种适用于航路规划的优化方法,可以为在敌方防御区域内执行攻击任务的无人机规划设计出高效的飞行航路,保证无人机以最小的被发现概率及可接受航程到达目标点,提高了无人机作战任务的成功率。仿真结果初步表明该方法是一种有效的航路规划方法。